# -*- coding: utf-8 -*-            
# @Time : 2023/9/18 22:14
# @Author  : lining
# @FileName: 合并k个升序链表.py
"""
https://leetcode.cn/problems/merge-k-sorted-lists/
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
__lt__ less than  当使用<时，自动调用这个方法,返回布尔值,重写该方法可自定义大小比较
自定义类中调用>时也是用的__lt__，只对调用值求反
__ge__ >=
__eq__  ==
__gt__  >

"""


class ListNode:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# 1,2,3
a1 = ListNode(3)
a2 = ListNode(2, a1)
a3 = ListNode(1, a2)
# 4,5,6
b1 = ListNode(6)
b2 = ListNode(5, b1)
b3 = ListNode(4, b2)


class PriorityQueue:
    # 优先队列，最小堆,数组存储，从1开始存储,父节点n，左子节点2n，右子节点2n+1
    def __init__(self):
        self.heap = [None]

    def pop(self):
        # 弹出堆顶,和最后一个元素交换，向下调整
        heap_len = len(self.heap)
        self.heap[1], self.heap[heap_len-1] = self.heap[heap_len-1],self.heap[1]
        node = self.heap.pop()
        self.heapifyDown(1)
        return node

    def insert(self,node):
        # 入队，插入末尾，向上调整,插入节点，取出值进行比较
        self.heap.append(node)
        self.heapifyUp(len(self.heap)-1)

    def heapifyUp(self, current):
        """
        :param current: 当前节点下标
        :return:
        """
        # 向上调整,当前节点current,父节点除2，向下取整
        parent_index = int(current / 2)
        if parent_index >= 1:
            if self.heap[current].value < self.heap[parent_index].value:
                # 当前节点小于父节点，交换
                self.heap[current],self.heap[parent_index] = self.heap[parent_index], self.heap[current]
                # 递归
                self.heapifyUp(parent_index)

    def heapifyDown(self, current):
        """
        :param current: 当前节点下标
        :return:
        """
        # 向下调整
        # 左子节点
        left_index = current*2
        # 右子节点
        right_index = current*2+1
        # 左右子节点都存在
        if len(self.heap)>right_index:
            # 获取比较小的值得下标
            min_index = left_index if self.heap[left_index].value < self.heap[right_index].value else right_index
            # 当前值比较大的交换
            if self.heap[current].value > self.heap[min_index].value:
                self.heap[current], self.heap[min_index]=self.heap[min_index],self.heap[current]
                self.heapifyDown(min_index)
            # 当前值已经更小，直接退出
            return
        # 只有左子节点,只需要做一次向下调整
        if len(self.heap)>left_index:
            if self.heap[current].value > self.heap[left_index].value:
                self.heap[current], self.heap[left_index] = self.heap[left_index], self.heap[current]

def merge(lists):
    """
    :param lists: 列表，传入每个链表头结点
    :return:
    """
    heap = PriorityQueue()
    # 先把链表的第一个元素放到队里
    for i in lists:
        # i,包含value和next
        if i is not None:
            heap.insert(i)
    # 结果链表的头结点
    head = ListNode(None)
    current = head
    while len(heap.heap)>1:
        # 弹出堆顶
        heap_node = heap.pop()
        node = ListNode(heap_node.value)
        current.next = node
        current = node
        # 补充弹出的堆顶的下一个数据
        if heap_node.next is not None:
            heap.insert(heap_node.next)
    return head


# a = [7,6,5,4,3,2,1]
# b = PriorityQueue()
# for i in a:
#     b.insert(i)
# print(b.heap)
# b.pop()
# print(b.heap)

x = merge([a3,b3])
print(x)